#!/usr/bin/env python3

"""
Given n non-negative integer a1, a2, ... an, where each represents a point at coordinate(i, ai).
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). 

Find two lines, which together with x-axis forms a container, such that the container contains the 
most water

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
"""


class Solution:
    def max_area(self, heights):
        start = 0
        end = len(heights) - 1
        max_area = None
        while start < end:
            area = min(heights[start], heights[end]) * (end - start)
            if max_area is None or area > max_area:
                max_area = area
            if heights[start] < heights[end]:
                small = heights[start]
                current = start + 1
                while current < end:
                    current_height = heights[current]
                    if current_height > small:
                        start = current
                        break
                    current += 1
                else:
                    return max_area
            else:
                small = heights[end]
                current = end - 1
                while current > start:
                    current_height = heights[current]
                    if current_height > small:
                        end = current
                        break
                    current -= 1
                else:
                    return max_area
                

if __name__ == '__main__':
    solution = Solution()
    assert 49 == solution.max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
